The present invention is advantageously applicable to a data retrieval process and apparatus such as in a process for retrieving place name data or address data from a large capacity map data storage for a navigation system. Although the application of the present invention is not limited to a navigation system, the present invention is described mainly with respect to the navigation system for convenience of explanation.
A navigation system, typically, a vehicle navigation system, performs travel guidance for enabling a user to easily reach a selected destination. Such a navigation system detects the position of the vehicle, reads out map data pertaining to an area at the vehicle current position from a data storage medium, for example, a CD-ROM (compact disk read-only memory) or a DVD (digital versatile disc). Typically, the vehicle position is determined by a self-contained navigation sensors (e.g. a distance traveled sensor and a bearing sensor) mounted in the vehicle and by a global positioning system (GPS) including a satellite (satellite navigation).
FIGS. 1A–1F show an example of overall procedure and screen display involved in the navigation system. FIGS. 1A–1D show an example of process for specifying a destination in the navigation system. When selecting a “Destination” menu on a main menu screen of FIG. 1A, the navigation system displays an “Find Destination By” screen as shown in FIG. 1B for specifying an input method for selecting the destination. The “Find Destination By” screen lists various methods for selecting the destination, which include “Address”, “Intersection”, “Point of Interest (POI)”, “Recent Route”, “Address Book”, and “Today's Plan”.
When selecting the “Address” method in FIG. 1B, the navigation system displays a keyboard screen as shown in FIG. 1C. Suppose the user inputs an address or a place name of the destination, the navigation system searches candidate destinations without waiting for full information is input by the user. For example, in FIG. 1C, when the user inputs “CA-11”, the navigation system retrieves address data that start with “CA-11”, such as “CA-112” and “CA-113”, although “CA-11” is only a part of the address.
When the retrieved data do not match the destination intended by the user, he inputs further digits of address as shown in FIG. 1D. Thus, in this example, the user inputs “CA-110”, then the navigation system retrieves addresses of the candidate destinations “CA-110” and “CA-1101”. Suppose the address “CA-1101” is the address of the destination where the user wants to go, he selects this address. The navigation system displays a “Confirm Destination” screen such as shown in FIG. 1E. If the name and address on the screen shows the correct destination, the user enters an “OK to Proceed” key to proceed to the next procedure.
The navigation system calculates and determines a route to the destination. Once the route to the destination is determined, the navigation system starts the route guidance as shown in FIG. 1F for guiding the user to the destination. Typically, the navigation system shows an intersection that is highlighted on the display to show the next turn and a direction of the turn. When the user approaches the destination within such a predetermined distance, the navigation system indicates that the destination is ahead.
During the process in which the user inputs an address of the destination, the navigation system predicts the full address to be input without waiting for the full data by the user. This is because by examining its database, the navigation system can tell that there are certain numbers of candidate address that would fit the input by the user so far. For example, in the case where the user is trying to input the street address of “CA-1101”, and has already input “CA-11” as shown in FIG. 1C, there are certain numbers of candidates that would be consistent with the input.
FIG. 2 shows an example of data stored in a data storage where the data is arranged in an alpha-numeric order. In this case, there are six (6) possible entries that can follow from the user's input “CA-11”. Namely, all of addresses “CA-112”, “CA-113”, “CA-114”, “CA-115”, “CA-1101” and “CA-1102” start with the specified input (search data) “CA-11”. In the data arrangement of the alpha-numeric order, the data is stored in the alphabetical as well as numerical order as shown in FIG. 2. Thus, the above noted six entries (recorded data) will be extracted by sequentially checking all of the entries of the data in the storage.
Namely, in the data arrangement of FIG. 2, there are a large volume of data that has to be searched before finding the first possible entry “CA-112”. Further, between the possible entry “CA-115” and the next possible entry “CA-1101” there are a large number of data entries which have to be checked. Therefore, it takes a long time to search and check the possible entries by a data retrieval system. It is especially true when the volume of data is large, such as several million entries in an address data file used in a typical navigation system.
More specifically, the dots between the entries indicates that there are other recorded data. In the example of FIG. 2, the address records ranging from “CA-112”to “CA-2101” are shown. After “CA-115”, the records that have numbers higher than “CA-115” are arranged so that such records as “CA-212” will follow. In order to accomplish the above function, the navigation system must be able to quickly search available address records as the user inputs a string of characters.
Because the address records are arranged in the alphanumeric order as noted above, the number “1101” comes long after the number “115”. As shown in FIG. 2, after the record “CA-115”, many records exist until the record “CA-1101” is reached. There may be several ten or hundred thousands of records to be searched in order to find all records that would fit the description. If the navigation system is going to check all the records to determine the number and records, it takes a long time to find all the desired records. The search time will directly reflect on the response time of the input display.